% AlgoDat ue4
% 12 Mai 2020

# Aufgabe 1

Es wird jeweils

$$ [17, 16, 11, 9, 20, 0, 3] $$

eingefügt. Weiters gilt $m = 7$.

## a

##### Disclosure

Die Ergebnisse wurden wie folgt berechnet:

```py
strlst@ayaya ue4 python3
>>> numbers = [17, 16, 11, 9, 20, 0, 3]
>>> [n % 7 for n in numbers]
[3, 2, 4, 2, 6, 0, 3]
```

$$ h(k) = k \mod m $$

$K_i$ bezeichne die Ketten der einzelnen Indizes zu Schritt $i$

Index|$K_1$|$K_2$|$K_3$|$K_4$|$K_5$|$K_6$|$K_7$
:-- |:--|:--|:--|:--|:--|:--|:--
0|  |  |  |          |  |0 |0
1|  |  |  |          |  |  |leer
2|  |16|16|16 $\to$ 9|16 $\to$ 9|16 $\to$ 9|16 $\to$ 9
3|17|17|17|17        |17|17|17 $\to$ 3
4|  |  |11|11        |11|11|11
5|  |  |  |          |  |  |leer
6|  |  |  |          |20|20|20

Beim Einfügen von 9 gibt es eine Kollision mit 16, da $h(16) = h(9) = 2$. In diesem Fall wird 9 einfach an die entsprechende Kette angehängt.

Beim Suchen von 9 wird die Kette an Index 2 hergenommen, da $h(9) = 2$, welche dann bis zum Ende linear durchsucht wird, um schließlich das Ergebnis zurückzuliefern.

Der durchschnittliche (erfolgreiche) Suchaufwand ergibt sich durch $\frac{\sum_{i}^{n} find(i)}{n} = \frac{9}{7} = 1.29$.

k|17||16||11||9||20||0||3||Summe
:--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--:
find(k)|1|+|1|+|1|+|2|+|1|+|1|+|2|=|9

## b

##### Disclosure

Die Ergebnisse wurden wie folgt berechnet:

```py
strlst@ayaya ue4 python3
>>> numbers = [17, 16, 11, 9, 20, 0, 3]
>>> import math
>>> def h(k):
...     return math.floor(7 * (k * math.sqrt(2) - math.floor(k * math.sqrt(2))))
>>> def hash(k, i):
...     return (h(k) + 1/2 * i + 1/2 * i * i) % 7
>>> [(n, int(hash(n, 0))) for n in numbers]
[(17, 0), (16, 4), (11, 3), (9, 5), (20, 1), (0, 0), (3, 1)]
>>> [(n, int(hash(n, 1))) for n in numbers]
[(17, 1), (16, 5), (11, 4), (9, 6), (20, 2), (0, 1), (3, 2)]
>>> [(n, int(hash(n, 2))) for n in numbers]
[(17, 3), (16, 0), (11, 6), (9, 1), (20, 4), (0, 3), (3, 4)]
>>> [(n, int(hash(n, 3))) for n in numbers]
[(17, 6), (16, 3), (11, 2), (9, 4), (20, 0), (0, 6), (3, 0)]
```

$$ h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m, c_1 = \frac{1}{2}, c_2 = \frac{1}{2} $$
$$ h'(k) = \lfloor m (k A - \lfloor k A \rfloor) \rfloor, A = \sqrt{2} $$

Index|$T_1$|$T_2$|$T_3$|$T_4$|$T_5$|$T_6$|$T_7$
:-- |:--|:--|:--|:--|:--|:--|:--
0|17|17|17|17|17|17|17
1|  |  |  |  |20|20|20
2|  |  |  |  |  |  |3 
3|  |  |11|11|11|11|11
4|  |16|16|16|16|16|16
5|  |  |  |9 |9 |9 |9 
6|  |  |  |  |  |0 |0 

Die Reihenfolge in der Indizes berechnet werden, wobei bei Kollisionen die Funktion $h(k, i)$ mit jeweils inkrementiertem Wert $i$ noch einmal aufgerufen wird, ist wie folgt:

$h(17, 0) = 0 \longrightarrow h(16, 0) = 4 \longrightarrow h(11, 0) = 3 \longrightarrow h(9, 0) = 5 \longrightarrow h(20, 0) = 1 \longrightarrow h(0, 0) = h(17, 0) = 0 \longrightarrow h(0, 1) = 1 \longrightarrow h(0, 2) = 3 \longrightarrow h(0, 3) = 6 \longrightarrow h(3, 0) = 1$, $h(3, 1) = 2$

Beim Suchen von 9 wird ergibt sich durch $h(9, 0) = 5$ der Index 5.

Der durchschnittliche (erfolgreiche) Suchaufwand ergibt sich durch $\frac{\sum_{i}^{n} find(i)}{n} = \frac{11}{7} = 1.57$.

k|17||16||11||9||20||0||3||Summe
:--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--:
find(k)|1|+|1|+|1|+|1|+|1|+|4|+|2|=|11

## c

##### Disclosure

Die Ergebnisse wurden wie folgt berechnet:

``` py
strlst@ayaya ue4 python3
>>> numbers = [17, 16, 11, 9, 20, 0, 3]
>>> def h_1(k):
...     return k % 7
>>> def h_2(k):
...     return (k % 5) + 1
>>> def hash(k, i):
...     return (h_1(k) + (i * h_2(k))) % 7
>>> [hash(n, 0) for n in numbers]
[3, 2, 4, 2, 6, 0, 3]
>>> [hash(n, 1) for n in numbers]
[6, 4, 6, 0, 0, 1, 0]
>>> [hash(n, 2) for n in numbers]
[2, 6, 1, 5, 1, 2, 4]
>>> [hash(n, 3) for n in numbers]
[5, 1, 3, 3, 2, 3, 1]
>>> [hash(n, 4) for n in numbers]
[1, 3, 5, 1, 3, 4, 5]
```

$$ h(k, i) = (h_1(k) + i h_2(k)) \mod m $$
$$ h_1(k) = k \mod m $$
$$ h_2(k) = (k \mod 5) + 1 $$

Index|$T_1$|$T_2$|$T_3$|$T_4$|$T_5$|$T_6$|$T_7$
:-- |:--|:--|:--|:--|:--|:--|:--
0|  |  |  |9 |9 |9 |9 
1|  |  |  |  |  |0 |0 
2|  |16|16|16|16|16|16
3|17|17|17|17|17|17|17
4|  |  |11|11|11|11|11
5|  |  |  |  |  |  |3 
6|  |  |  |  |20|20|20

Hier verläuft treten keine Kollisionen bis zum Schlüssel 9. Der Index für Schlüssel 9 ergibt sich dann durch $h(9, 1) = 0$. Weiters kollidiert 0, wo schließlich sich ein Index ergibt durch $h(0, 1) = 1$. Zuletzt kollidiert 3, mehrere Male sogar, wo sich schließlich ein Index ergibt durch $h(3, 4) = 5$.

Bei einer Suche nach 9 überprüfen wir zunächst Index 2, da $h(9, 0) = 2$. Weil dies unerfolgreich verläuft, überprüfen wir zunächst Index 0, da $h(9, 1) = 0$. An dieser Stelle wird 9 erfolgreich gefunden.

Der durchschnittliche (erfolgreiche) Suchaufwand ergibt sich durch $\frac{\sum_{i}^{n} find(i)}{n} = \frac{13}{7} = 1.86$.

k|17||16||11||9||20||0||3||Summe
:--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--:
find(k)|1|+|1|+|1|+|2|+|1|+|2|+|5|=|13

# Aufgabe 2

## a

Die alte Implementierung (I) ist folgende:

```java
public int hashCode() {
    int hash = 0;
    int skip = Math.max(1, length() / 8);
    for (int i = 0; i < length(); i += skip)
        hash = (hash * 37) + charAt(i);
    return hash;
}
```

Die neue Implementierung (II) ist folgende:

```java
public int hashCode() {
    int hash = 0;
    for (int i = 0; i < length(); i++)
        hash = (hash * 31) + charAt(i);
    return hash;
}
```

Es gibt zwei hauptsächliche Unterschiede. Zum einen ist die Konstante von 37 auf 31 geändert worden, aber das spielt für uns keine Rolle, weil beide Primzahlen sind. Der nächste Unterschied ist, dass kein `skip` mehr berechnet wird. Damit ändert sich die Zahl der Durchläufe, die sich so vergleichen lässt:

I)  Durchläufe $d_I$: $1 \leq d \leq length() / 8$
II) Durchläufe $d_{II}$: $1 \leq d \leq length()$

Es fällt natürlich auf, dass durch `skip` einfach Teile des Strings übersprungen werden. Dadurch lässt sich besonders leicht ein Beispiel für eine Kollision konstruieren:

```sh
strlst@ayaya ~ calc 24 / 8
3
strlst@ayaya ~ echo -n abcdefghijklmnopqrstuvwx | wc -c
24
strlst@ayaya ~ echo -n a11d11g11j11m11p11s11v11 | wc -c
24
```

Die Kollision lässt sich auch so verbildlichen:

```
012 012 012 012 012 012 012 012
abc def ghi jkl mno pqr stu vwx
a11 d11 g11 j11 m11 p11 s11 v11
```

Es wird durch `skip` nur jeder 3 Buchstabe (also unter einer Spalte mit "0") miteinbezogen. Für längere Strings ist die Menge an kollidierenden Zeichenfolgen sehr schnell sehr groß. Die neue Implementierung berücksichtigt alle Zeichen eines Strings.

Die Laufzeit beider Varianten unterscheidet sich um einen konstanten Faktor, nämlich 8, ist daher asymptotisch gleich performant.

## b

Die bessere Wahl ist jene, die weniger Kollisionen verursacht, also die ersten vier Zeichen. Da vorallem bei diesem Beispiel alle Studierenden beim selben E-Mail Provider sind, gibt es wenig bis gar keine Variation bei den letzten vier Zeichen und die Kollisionen werden zahlreich!

vorschlag: die meisten informationen mit einbeziehen
Ein Vorschlag wäre, zu versuchen die größtmögliche variierenden Stellen miteinzubeziehen. Vorallem da bei Studierenden der erste Buchstabe immer gleich ist, wäre es naheliegend, die letzten vier Stellen des Teils der E-Mail Adresse vor dem "@" miteinzubeziehen.

Ein Beispiel soll das illustrieren:

```
         ....
zufälligemail@addresse.com
         ^^^^           
```

## c

Angenommen unsere Hashfunktion nimmt ganzzahlige Zahlen $x \in \mathbb{N}$, dann lässt sich folgendes sagen:

$$ \forall x \in \mathbb{N} \forall n \in [0, m) : P(h(x) = n) = \frac{1}{m} $$

D.h., für arbiträre Eingaben $x$ ist die Wahrscheinlichkeit, als Ergebnis der Hashfunktion $h(k)$ genau $n$ zu bekommen, $1/m$, und das für alle $n$ zu diesen $x$.

Weiters definieren wir folgende Kenngröße, welche uns angibt, wie voll bereits die Hashtabelle ist:

$\alpha$ = k/m ... load factor, wobei $k$ die Anzahl der gerade gespeicherten Elemente ist, $k \leq m$

Die Laufzeit lässt sich eingrenzen durch eine *worst-case* und *best-case* Analyse. Da im *best-case* immer das entsprechende Element sofort gefunden wird (auch bei voller Hashtabelle), können wir eine *best-case* Laufzeitkomplexität von $O(1)$ observieren. Da im *worst-case* immer alle Elemente durchsucht werden, und die Hashtabelle höchstens $m$ Elemente besitzt, wobei gilt $n \in [0, m)$, können wir eine *worst-case* Laufzeitkomplexität von $O(n)$ erwarten.

Abhängig wie viele Elemente durchschnittlich pro Index $n$ belegt sind, varriert die Performance. $\alpha$ als Kenngröße sagt uns, wie lang durchschnittlich eine Kette ist. Für jeweils unerfolgreiche Suche, sowie erfolgreiche Suche nach einem beliebigen Element, erwarten wir also $\alpha$ Elemente durchgehen zu müssen (leider entgeht hier das entsprechende Werkzeug, um einen statistisch korrekten Beweis zu führen). Wenn wir auch noch den Fall $k = 0$ berücksichtigen, dann können wir sagen, die *average-case* Laufzeitkomplexität fällt auf $O(\alpha + 1)$.


# Aufgabe 3

## a

In diesem Beispiel besteht die Hash Tabelle aus 3 möglichen Indizes, $m = 3$. Die Hashfunktion nimmt jeweils den ersten Buchstaben eines Strings und mapped diese auf die Indizes der Hashtabelle.

```
A:
B:
C:
```

$$ h(name) = upper(name[0]) $$

Wenn wir jetzt zwei Datensätze einfügen:

```
insert(alpha)
insert(aleph)
```

entsteht folgende Tabelle:

```
A: alpha
B: aleph
C:
```

Durch löschen von dem ersteren Datensatz:

```
delete(alpha)
```

entsteht dann folgende Tabelle:

```
A:
B: aleph
C:
```

Problematisch ist nun eine Suche nach dem zweiten Datensatz, `find(aleph)` hört nämlich gleich zu Beginn der Suche auf, obwohl *aleph* enthalten ist!

## b

$$ h(k) = k \mod m, m = 7 $$

```
0:
1:
2:
3:
4:
5:
6:
```

Wir fügen nun der Reihe nach die Elemente 1, 2, 8, 15 und 9 ein. Die Hashtabelle sieht dann wie folgt aus:

```
0:
1: 1
2: 2
3: 8
4: 15
5: 9
6:
```

Wenn wir jetzt nach dem Schema das Element 1 löschen, werden wir wegen $h(1) = 1$ das Element an Index $i = 1$ entfernen. Wir suchen nun ein kleinstmögliches $j$, sodass $T[(i + j + 1) \mod m] = leer$ und $T[(i + j + 1) \mod m] \neq leer$. Diese zwei Stellen finden sich an Indizes 5 und 6, sodass $j = 4$. Wenn wir jetzt einfach das Element an Index $(i + j) = 5$ verschieben an Index $i = 1$, dann kann zwar jedes Element für das gilt $h(k) = 1$ immer noch gefunden werden, aber nicht zwingend jedes Element für das gilt $h(k) = 2$. Inzwischen sieht unsere Tabelle wie folgt aus:

```
0:
1: 9
2: 2
3: 8
4: 15
5:
6:
```

Eine Suche nach 9 würde nur dann funktionieren, wenn die Hashtabelle von Index 2 beginnend bis Index 1 vollständig gefüllt ist (wobei an der Grenze 6 wieder bei 0 angefangen wird zu zählen)! Weil dies nicht der Fall ist und die Suche bei Index 4 bereits abbricht, kann 9 nicht gefunden werden, obwohl dieses enthalten ist.

## c

Man könnte den zu löschenden Eintrag entfernen und die gesamte Hashtabelle rekonstruieren. Natürlich ist das mit einer sehr ungünstigen Laufzeit von $\Omega(n)$ für jede Löschoperation verbunden.

Eine klügere Variante wäre es, zu versuchen, den Zustand vor einfügen des zu löschenden Eintrags wiederherzustellen. Dabei beginnen wir bei $i$, an wessen Stelle wir das Element löschen. Nun iterieren wir von dieser Stelle aus die restliche Liste. In jedem Schritt speichern wir uns unter *last* den Eintrag den wir eben betrachten, wenn folgendes gilt:

- $h(T[i]) = i$

D.h., die Hashfunktion liefert uns für das Element das wir gerade betrachten Index $i$. Das bedeutet, dass dieses Element ursprünglich dafür vorgesehen war, an Stelle $i$ platziert zu werden, aber es durch eine Kollision weiterversetzt wurde. Wir hören auf zu iterieren, sobald folgendes eintritt:

- $T[i]$ ist ein (tatsächlich) freier Eintrag

*last* sollte nun das letzte Element der Hashtabelle beinhalten, welches an die Stelle $i$ an der wir gelöscht haben eingefügt worden wäre. Aber wir müssen vorsichtig sein, wir müssen nachdem wir *last* nach $i$ verschoben haben, dasselbe noch einmal durchführen, diesmal mit dem Index von *last*, damit wir die Suche nach Elementen für jene die Hashfunktion andere Indizes berechnet nicht zerstören.

# Aufgabe 4

## a

Bloom Filter besitzen eine ähnliche Charakteristiken zu Hash Tabellen, nämlich unterstützt ein Bloom Filter äußerst performante Operationen für Suche und Einfügen. Während aber bei Hashtabellen normalerweise das Element selbst gespeichert wird und diese Daten abrufbar sein sollen, geht es bei Bloom Filter nur um die *Existenz* von Elementen. Das ergibt eine außerordentliche Platzeffizienz. Eine beispielhafte Anwendung in einer praktischen Datenstruktur wäre HashSet, wobei aber auf eine Eigenschaft Acht zu nehmen ist.

Bloom Filter können *false positives* haben. D.h., ein Element, dass nie eingefügt wurde, könnte dennoch gefunden werden. Umgekehrt aber gibt es keine *false negatives*, es kann nie etwas nicht gefunden werden, was schon eingefügt wurde.

Löschen ist eine komplizierte Angelegenheit, und viele Variationen unterstützen diese Operation gar nicht.

Allgemein kann ein Bloom Filter als Funktion definiert werden, welche auf beliebige Eingangsdaten $M$ operieren und im Hintergrund ein $m$ bit langes Datenwort speichern. Dabei sind sind Einfügen und Suchen dann folgende Funktionen:

$$ B_{insert} : M \to W, W = (w_0, w_1, ..., w_{m - 1}) $$

$$ B_{find} : M \to \{ true, false \} $$

Dabei basiert dieses abbilden auf mehrere Hashfunktionen, in unserem Fall die Menge an Hashfunktionen $H = \{ h_1, h_2, ..., h_k \}$.

Pseudo Code würde für diese Funktionen wie folgt aussehen:

x ... Eingangsdaten, $x \in M$

W ... Wort in welches eingefügt werden soll, $W = (w_0, w_1, ..., w_{m - 1})$

```
insert(W, x):  
for i = 1, 2, ..., k  
    W[h_i(x)] = 1
```

```
find(W, x):
for i = 1, 2, ..., k
    if not W[h_i(x)]:
        return false
return true
```

Der Speicheraufwand ist daher (erstaunlicherweise) exakt $m$ bit. Der Laufzeitaufwand ist dann höchstens ein vielfaches der aufwendigsten Hashfunktion aus $H$.

## b

##### Disclosure

Die Ergebnisse wurden wie folgt berechnet:

```py
strlst@ayaya ~ python3
Python 3.8.2 (default, Mar 24 2020, 03:08:36)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def h_1(k):
...     return ((2**k) % 11) - 1
...
>>> def h_2(k):
...     return ((5**k) % 11) - 1
...
>>> def h_3(k):
...     return ((7**k) % 11) - 1
...
>>> numbers = [2, 4]
>>> [(h_1(n), h_2(n), h_3(n)) for n in numbers]
[(3, 2, 4), (4, 8, 2)]
>>> numbers2 = [3, 5, 6]
>>> [(h_1(n), h_2(n), h_3(n)) for n in numbers2]
[(7, 3, 1), (9, 0, 9), (8, 4, 3)]
```

$$ h_1(k) = (2^k mod (m + 1)) - 1, m = 10 $$
$$ h_2(k) = (5^k mod (m + 1)) - 1, m = 10 $$
$$ h_3(k) = (7^k mod (m + 1)) - 1, m = 10 $$

Es sollen nun 2 und 4 eingefügt werden. In der folgenden Tabelle sind die jeweiligen Worte und die darauf angewendeten Operationen festgehalten.

Index | `0123456789`
:--|:--
Wort W| `0000000000`, insert(2)
Wort W| `0011100000`, insert(4)
Wort W| `0011100010`

## c

Es sollen nun 3, 5 und 6 gesucht werden. Die Bitmuster der einzelnen Eingangsdaten und des Wortes W sind folgende:

Index|`0123456789`
:--  |:--
3    |`0101000100`
5    |`0000000001`
6    |`0001100010`
W    |`0011100010`

Wie sich erkennen lässt, scheiden 3 und 5 sehr schnell aus, weil sie bits enthalten, die unser Wort nicht enthält. `find` liefert also $false$. Aber W enthält alle bits, die die gehashte 6 enthalten würde. `find` liefert also $true$. Es handelt sich hier um ein *false positive*!

# Aufgabe 5

## a

In der offiziellen [Python HowTo Seite (link)](https://wiki.python.org/moin/HowTo/Sorting/) wird Timsort erwähnt und [Wikipedia (link)](https://en.wikipedia.org/wiki/Timsort) verlinkt. Timsort haben wir in der Vorlesung kennengelernt, aber hier noch mal ein Auszug aus dem verlinkten Wikipedia Eintrag:

> "Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] in GNU Octave,[6] on V8,[7] and Swift.[8]"

Aus der [PHP Dokumentation (link)](https://www.php.net/manual/en/function.sort.php):

> "Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort. The pivot is chosen in the middle of the partition resulting in an optimal time for already sorted arrays. This is however an implementation detail you shouldn't rely on."

## b

[(Quelle für die Angaben (link))](https://en.wikipedia.org/wiki/Introsort)

Introsort verbindet drei Sortieralgorithmen, die jeweils ihre eigenen Vorteile haben. Zum Beispiel haben wir in der Vorlesung gehört, dass für wirklich wenige Elemente, Insertionsort sehr gut abschneidet. Dabei ist die Strategie bei Introsort nicht besonders kompliziert:

- verwende Quicksort
- ab einer gewissen Rekursionstiefe, wechsle für die derzeit betrachtete Menge zu Heapsort
- ab einer gewissen Untergrenze für die Anzahl der derzeit betrachteten Menge, wechsle zu Insertionsort

Mit diesem Ansatz wird Insertionsort für seine effizienten Fälle herangezogen, nämlich bei sehr wenigen Elementen. Bei sehr wenigen Elementen entsteht nämlich ein vergleichsweise großer Overhead bei anderen Algorithmen. Ähnlich ist die Situation für Quicksort. Im *worst-case* liefert Quicksort nämlich eine Laufzeitkomplexität von $O(n^2)$. Bevor das passieren kann, wird zu Heapsort gewechselt, um dennoch eine Laufzeitkomplexit von $(n \cdot log(n))$ zu gewährleisten. Dabei verhält sich diese Rekursionstiefe (also hängt ab von) logarithmisch zur Eingabegröße.

Introsort funktioniert zwar *in place*, ist aber nicht stabil.

## c

Da bei herkömmlichen Bubblesort ein Wertepaar $(A[i - 1], A[i]), 0 < i < n$ nur getauscht wird, wenn gilt $A[i - 1] > A[i]$, werden gleichwertige Wertepaare nicht getauscht. Da zusätzlich bei herkömmlichen Bubblesort Implementierungen von links bis rechts iteriert wird, bleibt die Ordnung gleicher Elemente bestehen. Bubblesort ist also stabil.

# Aufgabe 6

## a

(durch `pdflatex` Formatierung könnten die Grafiken nicht an richtiger Stelle sein)

Wir sollen mithilfe einer Priority Queue (implementiert als Heap) und des Prim Algorithmus' den in Fig.1 abgebildeten Graphen zu einem Spanning Tree wandeln.

![originaler Graph](./res/graph.png){ width=50% }

Der finale Spanning Tree lässt sich dann in Fig.2 observieren. Die Reihenfolge in der die jeweiligen Kanten hinzugefügt worden sind, lässt sich aus den individuellen Heap Stadien ablesen, aber zur lesbarkeit wurden diese Stadien auf die Kanten des Spanning Trees abgebildet.

![finaler Spanning Tree](./res/spanning-tree.png){ width=50% }

Wie sich der Heap entwickelt lässt sich in Fig.3 observieren. Wobei der erste Heap eines Stadiums immer der initiale Zustand ist, der optionale Mittelschritt die *updates* der Kantengewichte und der letzte Schritt der Heap nach den Updates.

![Heap Entwicklung](./res/heap-stages.png){ width=75% }

## b

In diesem Fall sind wir konfrontiert mit Situationen in denen wir ein Element haben und dessen Heap Gewicht verringern wollen. In einer Array-Repräsentation werden die Heap Elemente vermutlich bewegt werden, also ist es schwer, rein durch clevere Ansätze das Problem zu lösen. Eine Datenstruktur aber, die in letzter Zeit sehr vielversprechende Performance für das *Einfügen* und *Finden* von Datensätzen gezeigt hat, könnte das Problem lösen: die Hashtabelle.
Nämlich können Elemente selbst als *keys* und *values* verwendet werden. Benötigen wir ein bestimmtes Element, finden wir es einfach mithilfe der Hashtabelle und operieren weiter mit Heap Operationen darauf.

Klarerweise stellt dies einen erhöhten Speicherbedarf dar, aber auf die Laufzeit wirkt sich diese zusätzliche Datenstruktur positiv aus: sobald die Hashtabelle initialisiert ist (kann zur selben Zeit mit dem Heap mit derselben Laufzeitkomplexität des Heaps gemacht werden), können Elemente in nahezu konstanter Zeit gefunden werden. Selbst wenn Elemente aus dem Heap entfernt werden, könnte eine Hashtabelle, die bereits aus dem Heap entfernte Elemente *nicht* entfernt, dennoch dieselbe Effizienz beweisen.

Da die zusätzliche Laufzeitkomplexität der jeweiligen Hashtabellenoperationen nur additiv dazugezählt werden müssen, und die Laufzeit der Heap Operationen für eine Hashtabelle obere Schranken darstellen, präservieren wir die Laufzeitkomplexität der Heap Operationen.
